class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        map<char, char> matchMap;
        matchMap['('] = ')';
        matchMap['['] = ']';
        matchMap['{'] = '}';

        for (auto ch : s)
        {
            if (matchMap.count(ch))
            {
                st.push(ch);
            }
            else
            {
                if (st.empty())
                {
                    return false;
                }
                char topVal = st.top();
                st.pop();
                if (matchMap[topVal]!=ch)
                {
                    return false;
                }
            }
        }
        return st.empty();
    }
};
